1731C - Even Subarrays - CodeForces Solution

#include <algorithm>
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define endl "\n"
#define output(a) cout<<a<<endl;
#define outputv(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define outputp(a) cout<<a.first<<" "<<a.second<<endl;
#define all(v) v.begin(), v.end()
#define yes cout<<"YES"<<endl;return;
#define no cout<<"NO"<<endl;return;
#define pii pair<int,int>
using ll = long long;
const ll MOD = 1e9 + 7;
using namespace std;

void soln()
{
 	ll n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> pre(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pre[i] = pre[i-1]^a[i];
    }

    vector<int> sq;
    {
        for(int i=0;i*i<=(2*n)+1;i++){sq.push_back(i*i);}
    }
    
    int maxe = *max_element(1 + all(pre));
    ll exist_odd = 0;
   
    for(auto i:sq)
    {
        vector<int> seen_till_now(maxe + 1,0);
        //cout<<i<<endl;
        for(int j=1;j<=n;j++)
        {
            int req = (i^pre[j]);
            if(req > maxe){seen_till_now[pre[j]]++;continue;}
            if(req == 0){exist_odd+=1;}
       //   if(seen_till_now[req]>0){cout<<j<<" ";}
            exist_odd += seen_till_now[req];
            seen_till_now[pre[j]]++;
        }
        //cout<<endl;
    }
    cout<<(n*(n+1))/2 - exist_odd<<endl;
}

signed main() {
#ifdef LOCAL_PROJECT
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
 freopen("error.txt", "w", stderr);
#endif
IOS
ll t;
t=1;
cin>>t;
while(t--)  
{
 soln();  
}
return 0;
}